package com.fengye.algorithms.huawei;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * https://www.nowcoder.com/practice/196534628ca6490ebce2e336b47b3607?tpId=37&tags=&title=&difficulty=0&judgeStatus=0&rp=1&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37
 * @Author fengye
 * @Date 2023/4/7 10:20
 **/
public class PrimeFactorMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int num = in.nextInt();
        if (num == 1) {
            return;
        }
        if (num == 2) {
            System.out.println(num);
            return;
        }
        List<Integer> list = new ArrayList<>();
        // 先保证不是偶数了
        while (num % 2 == 0) {
            num /= 2;
            list.add(2);
        }
        for (int i = 3; i <= num; i+=2) {
            // 处理奇数
            while (num % i == 0) {
                num /= i;
                list.add(i);
            }
            // 剑走偏锋，发现一个规律，后面的数如果二进制是101或111，也是质数
            if (num > 100000) {
                String str2 = Integer.toString(num, 2);
                int length = str2.length();
                String subStr = str2.substring(length - 3, length);
                if (subStr.equals("101") || subStr.equals("111")) {
                    list.add(num);
                    break;
                }
            }
        }

        for (int i : list) {
            System.out.print(i + " ");
        }
    }

}
